package com.ssh;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class GenerateParenthesis_22 {
	public List<String> generateParenthesis(int n) {
		List<String> list = new ArrayList<String>();
		backtrack(list, "", 0, 0, n);
		return list;
    }
    private void backtrack(List<String> list, String str, int open, int close, int max){
    	if (str.length() == 2 * max) {
    		list.add(str);
    		return;
    	}
    	if (open < max) {
    		backtrack(list, str+"(", open+1, close, max);
    	}
    	if (close < open) {
    		backtrack(list, str+")", open, close+1, max);
    	}
    }
    @Test
    public void test () {
    	System.out.println(generateParenthesis(3));
    }
}
